Algoritmo de Paxos

El algoritmo de Paxos es un algoritmo para llegar a consensos en sistemas distribuidos con cierto grado de tolerancia a fallos. Entendemos consenso como el proceso de ponerse de acuerdo sobre uno de los resultados entre un grupo de participantes. Este problema se hace difícil cuando los participantes o su medio de comunicación puede experimentar fallos.

El protocolo Paxos primero fue publicado en 1989 por Leslie Lamport aunque pasó desapercibido hasta 1998 cuando lo publicó en una revista especializada. Desde entonces se han publicado varias mejoras y adaptaciones.^[1]​

El algoritmo incluye una gama de soluciones de compensación entre el número de procesos, el número de mensajes con retraso antes de aprender el valor acordado, el nivel de actividad de los participantes, el número de mensajes enviados, y los tipos de fallos. Aunque un protocolo de consenso con tolerancia a fallos determinista no puede garantizar el progreso en una red asíncrona, Paxos garantiza la seguridad (libre de inconsistencia), y las condiciones que podrían hacer que no progrese son difíciles de ocurrir.

Funciona en el modelo de paso de mensajes con asincronía y con menos n/2 fallos (pero no con fallos bizantinos). El algoritmo de Paxos garantiza que se llegará a un acuerdo y garantiza la finalización si hay un tiempo suficientemente largo sin que ningún proceso reinicie el protocolo.

1. ↑ Consensus on a multicore machine. Roni Häcki. 2015. Systems Group, Department of Computer Science, ETH Zurich